package Week.D008;

import common.ListNode;
import org.junit.Test;

import java.util.*;

public class Solution03 {
    public List<Integer> shortestDistanceColor(int[] colors, int[][] queries) {
        List<Integer> result = new ArrayList<>();

        List<Integer> col1 = new ArrayList<>();
        List<Integer> col2 = new ArrayList<>();
        List<Integer> col3 = new ArrayList<>();
        for (int i = 0; i < colors.length; i++) {
            if (colors[i] == 1) {
                col1.add(i);
            } else if (colors[i] == 2) {
                col2.add(i);
            } else {
                col3.add(i);
            }
        }

        for (int[] q : queries) {
            if (q[1] == 1) {
                result.add(getResult(q[0], col1));
            }
            else if (q[1] == 2) {
                result.add(getResult(q[0], col2));
            }
            else {
                result.add(getResult(q[0], col3));
            }
        }
        return result;
    }



   private int getResult(  int search,List<Integer> col){

        if(col.size()==0){
            return -1;
        }
        int result=Integer.MAX_VALUE;
        int start=0;int end=col.size()-1;
        while (start<=end){
            int mid=(start+end)/2;
            result=Math.min(Math.abs(search-col.get(mid)),result);
            if(search>col.get(mid)){
                start=mid+1;
            }else {
                end=mid-1;
            }
        }
        return result;
   }
    @Test
    public void test(){
        int[] colors= new int[]{1,1,2,1,3,2,2,3,3};
        int[][] qs=new int[][]{{1,3},{2,2},{6,1}};
        List<Integer> parentPath=shortestDistanceColor(colors,qs);
        System.out.println(parentPath);
    }
}
